package DFS;

import java.util.ArrayList;

/**
 * @Author: dust
 * @Date: 2019/11/18 16:27
 */
public class FindBridges {

    private Graph G;
    private boolean[] visited;
    private int ord[];
    private int low[];
    private int cnt;

    private ArrayList<Edge>res=new ArrayList<>();

    public ArrayList<Edge> result(){
        return res;
    }

    public FindBridges(Graph G) {

        this.G=G;
        visited=new boolean[G.V()];
        ord=new int[G.V()];
        low=new int[G.V()];
        cnt=0;
       for(int v=0;v<G.V();v++){
           if(!visited[v]){
               dfs(v,v);
           }
       }
    }

    private void dfs(int v,int parent){

        visited[v]=true;
        ord[v]=cnt;
        low[v]=ord[v];
        cnt++;

        for(int w:G.adj(v)){
            if(!visited[w]){
                dfs(w,v);
                low[v]=Math.min(low[v],low[w]);
                if(low[w]>ord[v]){
                    //vw是桥
                    res.add(new Edge(v,w));
                }
            }else if(w!=parent){
                low[v]=Math.min(low[w],low[v]);
            }
        }

    }

    public static void main(String[] args) {
        Graph g=new Graph("g3.txt");
        FindBridges dfs=new FindBridges(g);
        System.out.println(dfs.result());
    }

}
